package leetcode.code0132;

import java.util.Arrays;

/**
 * 执行用时：18 ms, 在所有 Java 提交中击败了77.46%的用户
 *
 * 内存消耗：39.7 MB, 在所有 Java 提交中击败了63.23%的用户
 *
 * 通过测试用例：33 / 33
 */
public class Solution extends Solution132 {

	@Override
	public int minCut(String s) {
		int len = s.length();
		char[] cc = s.toCharArray();
		boolean[][] is = new boolean[len + 1][len + 1];
		int[] dp = new int[len + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		for (int R = 1; R <= len; R++) {
			is[R][R] = true;
			char left = cc[R - 1];
			boolean flag = true;
			if (is[1][R - 1]) {
				dp[R - 1] = 0;
				flag = false;
			}
			for (int L = 1; L < R; L++) {
				char right = cc[L - 1];
				if (L + 1 == R) {
					is[L][R] = (left == right);
				} else {
					is[L][R] = left == right && is[L + 1][R - 1];
				}
				if (flag) {
					if (is[L + 1][R - 1]) {
						dp[R - 1] = Math.min(dp[R - 1], dp[L] + 1);
					}
				}
			}

		}
		if (is[1][len]) {
			return 0;
		} else {
			for (int j = 1; j < len; j++) {
				if (is[j + 1][len]) {
					dp[len] = Math.min(dp[len], dp[j] + 1);
				}
			}
		}
		return dp[len];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
//		so.debug3();
		so.debug4();
//		so.debug5();

	}

}
